1\documentclass{article}
2
3\usepackage{fancyhdr}
4\usepackage{extramarks}
5\usepackage{amsmath}
6\usepackage{amsthm}
7\usepackage{amsfonts}
8\usepackage{mathabx}
9\usepackage{tikz}
10\usepackage[plain]{algorithm}
11\usepackage{algpseudocode}
12\usepackage{rotating}
13\usepackage{stmaryrd}
14
15\usetikzlibrary{automata,positioning}
16
17%
18% Basic Document Settings
19%
20
21\topmargin=-0.45in
22\evensidemargin=0in
23\oddsidemargin=0in
24\textwidth=6.5in
25\textheight=9.0in
26\headsep=0.25in
27
28\linespread{1.1}
29
30\pagestyle{fancy}
31\lhead{\hmwkAuthorName}
32\chead{\hmwkClass\ (\hmwkClassInstructor): \hmwkTitle}
33\rhead{\firstxmark}
34\lfoot{\lastxmark}
35\cfoot{\thepage}
36
37\renewcommand\headrulewidth{0.4pt}
38\renewcommand\footrulewidth{0.4pt}
39
40\setlength\parindent{0pt}
41
42%
43% Create Problem Sections
44%
45
46\newcommand{\enterProblemHeader}[1]{
47 \nobreak\extramarks{}{Le problème \arabic{#1} se poursuit sur la page suivante\ldots}\nobreak{}
48 \nobreak\extramarks{Problème \arabic{#1} (poursuit)}{Le problème \arabic{#1} se poursuit sur la page suivante\ldots}\nobreak{}
49}
50
51\newcommand{\exitProblemHeader}[1]{
52 \nobreak\extramarks{Problème \arabic{#1} (poursuit)}{Le problème \arabic{#1} se poursuit sur la page suivante\ldots}\nobreak{}
53 \stepcounter{#1}
54 \nobreak\extramarks{Problème \arabic{#1}}{}\nobreak{}
55}
56
57\setcounter{secnumdepth}{0}
58\newcounter{partCounter}
59\newcounter{homeworkProblemCounter}
60\setcounter{homeworkProblemCounter}{1}
61\nobreak\extramarks{Problème \arabic{homeworkProblemCounter}}{}\nobreak{}
62
63%
64% Homework Problem Environment
65%
66% This environment takes an optional argument. When given, it will adjust the
67% problem counter. This is useful for when the problems given for your
68% assignment aren't sequential. See the last 3 problems of this template for an
69% example.
70%
71\newenvironment{homeworkProblem}[1][-1]{
72 \ifnum#1>0
73 \setcounter{homeworkProblemCounter}{#1}
74 \fi
75 \section{Problème \arabic{homeworkProblemCounter}}
76 \setcounter{partCounter}{1}
77 \enterProblemHeader{homeworkProblemCounter}
78}{
79 \exitProblemHeader{homeworkProblemCounter}
80}
81
82%
83% Homework Details
84% - Title
85% - Due date
86% - Class
87% - Section/Time
88% - Instructor
89% - Author
90%
91
92\newcommand{\hmwkTitle}{Khôlle 2}
93\newcommand{\hmwkDueDate}{2024/09/27}
94\newcommand{\hmwkClass}{Maths}
95\newcommand{\hmwkClassInstructor}{M. Fourre}
96\newcommand{\hmwkAuthorName}{\textbf{Louis Dalibard}}
97
98%
99% Title Page
100%
101
102\title{
103 \vspace{2in}
104 \textmd{\textbf{\hmwkClass:\ \hmwkTitle}}\\
105 \normalsize\vspace{0.1in}\small{\hmwkDueDate}\\
106 \vspace{0.1in}\large{\textit{\hmwkClassInstructor}}
107 \vspace{3in}
108}
109
110\author{\hmwkAuthorName}
111\date{}
112
113\renewcommand{\part}[1]{\textbf{\large Part \Alph{partCounter}}\stepcounter{partCounter}\\}
114
115%
116% Various Helper Commands
117%
118
119% Useful for algorithms
120\newcommand{\alg}[1]{\textsc{\bfseries \footnotesize #1}}
121
122% For derivatives
123\newcommand{\deriv}[1]{\frac{\mathrm{d}}{\mathrm{d}x} (#1)}
124
125% For partial derivatives
126\newcommand{\pderiv}[2]{\frac{\partial}{\partial #1} (#2)}
127
128% Integral dx
129\newcommand{\dx}{\mathrm{d}x}
130
131% Alias for the Solution section header
132\newcommand{\solution}{\textbf{\large Solution}}
133
134% Probability commands: Expectation, Variance, Covariance, Bias
135\newcommand{\E}{\mathrm{E}}
136\newcommand{\Var}{\mathrm{Var}}
137\newcommand{\Cov}{\mathrm{Cov}}
138\newcommand{\Bias}{\mathrm{Bias}}
139
140\begin{document}
141
142\maketitle
143
144\pagebreak
145
146\begin{homeworkProblem}
147 Soit $F$ un ensemble fini.\\
148 Soit $E=P(F)$\\
149 Ecrire $A \subseteq B$ sous forme d'intersection de relations d'ordre totales dans une famille $( \preccurlyeq _i )_{i\in I}$\\\\
150 \subsection{Définitions}
151 Notons $n=|F|$\\
152 $F$ est fini donc on peut numéroter ses élements.\\
153 $G=\{0,1,2,3,...,n-1\}$\\
154 tel que $F \simeq G$ avec $g$ une bijection associant un unique nombre entre $1$ et $n-1$ pour chaque élement de $F$
155 On peut donc poser la bijection suivante $f: P(F) \rightarrow \llbracket 0;2^n-1\rrbracket$\\
156 \hspace*{7cm} $X \mapsto \sum_{x \in X}2^{g(x)}$
157 \\
158
159 Prenons $I=F$
160
161 Pour tout $i \in I$\\
162 On définit la relation $ \preccurlyeq _i $ sur $E$ tel que $A \preccurlyeq _i B \iff (|A\cap \{i\}| < |B\cap \{i\}| \text{ ou } (|A\cap \{i\}| = |B\cap \{i\}| \text{ et } f(g(A)) \leq f(g(B)))$
163
164 Montrons que pour tout $i \in I, \preccurlyeq _i $ est une relation d'ordre totale.
165 \subsubsection{Réflexivité}
166 Soit $A \in E$\\
167 $A \preccurlyeq _i A$ car $|A\cap \{i\}| = |A\cap \{i\}|$ et $f(g(A))=f(g(A))$
168 \subsubsection{Anti-symétrie}
169 Soit $A,B \in E$, tel que $A \preccurlyeq _i B$ et $B \preccurlyeq _i A$\\
170 $|A\cap \{i\}| < |B\cap \{i\}|$ et $|A\cap \{i\}| > |B\cap \{i\}|$ impossible donc $|A\cap \{i\}| = |B\cap \{i\}|$\\
171
172 Donc $f(g(A)) \leq f(g(B))$ et $f(g(A)) \geq f(g(B))$\\
173 Donc $f(g(A)) = f(g(B))$
174 Donc $A = B$ par injectivité de $g$ puis de $f$
175 \subsubsection{Transitivité}
176 Soit $A,B,C \in E$, tel que $A \preccurlyeq _i B$ et $B \preccurlyeq _i C$\\
177 Plusieurs cas possibles:
178 \begin{itemize}
179 \item $|A\cap \{i\}| < |B\cap \{i\}|$ et $|B\cap \{i\}| < |C\cap \{i\}|$\\
180 Donc $|A\cap \{i\}| < |C\cap \{i\}|$ et donc $A \preccurlyeq _i C$
181 \item $|A\cap \{i\}| = |B\cap \{i\}| \text{ et } f(g(A)) \leq f(g(B))$ et $|B\cap \{i\}| < |C\cap \{i\}|$\\
182 Donc $|A\cap \{i\}| < |C\cap \{i\}|$ et donc $A \preccurlyeq _i C$
183 \item $|A\cap \{i\}| < |B\cap \{i\}|$ et $|B\cap \{i\}| = |C\cap \{i\}| \text{ et } f(g(B)) \leq f(g(C))$\\
184 Donc $|A\cap \{i\}| < |C\cap \{i\}|$ et donc $A \preccurlyeq _i C$
185 \item $|A\cap \{i\}| = |B\cap \{i\}| \text{ et } f(g(A)) \leq f(g(B))$ et $|B\cap \{i\}| = |C\cap \{i\}| \text{ et } f(g(B)) \leq f(g(C))$\\
186 Donc $|A\cap \{i\}| = |C\cap \{i\}|$ et $f(g(A)) \leq f(g(C))$ et donc $A \preccurlyeq _i C$
187
188
189 \end{itemize}
190 \subsubsection{Relation d'ordre totale}
191 Soit $A,B \in E$
192 4 cas possibles
193 \begin{itemize}
194 \item $|A\cap \{i\}| < |B\cap \{i\}|$\\
195 Donc $A \preccurlyeq _i B$
196 \item $|B\cap \{i\}| < |A\cap \{i\}|$\\
197 Donc $B \preccurlyeq _i A$
198 \item $|A\cap \{i\}| = |B\cap \{i\}| \text{ et } f(g(A)) \leq f(g(B))$\\
199 Donc $A \preccurlyeq _i B$
200 \item $|A\cap \{i\}| = |B\cap \{i\}| \text{ et } f(g(A)) \geq f(g(B))$\\
201 Donc $B \preccurlyeq _i A$
202
203 Donc $\forall A,B \in E,\quad A \preccurlyeq _i B \text{ ou } B \preccurlyeq _i A$
204
205
206 \end{itemize}
207
208 \subsection{Conclusion}
209 Soit $A,B \in E$\\
210 Montrons que $A \subseteq B \iff \forall x \in I, A \preccurlyeq _i B$ par double implication.\\
211 \subsubsection{Sens 1: Supposons $A \subseteq B$}
212 $Soit x \in I$
213 Trois cas de figure possible:\\
214 \begin{itemize}
215 \item $|A\cap \{i\}| = 0 \text{ et } |B\cap \{i\}| = 1$\\
216 $|A\cap \{i\}| < |B\cap \{i\}|$\\
217 et dans ce cas là $A \preccurlyeq _i B$
218 \item $|A\cap \{i\}| = 1 \text{ et } |B\cap \{i\}| = 1$
219 $|A\cap \{i\}| = |B\cap \{i\}|$\\
220 et dans ce cas là $f(g(A)) \geq f(g(B))$\\
221 Donc $A \preccurlyeq _i B$
222 \item $|A\cap \{i\}| = 0 \text{ et } |B\cap \{i\}| = 0$
223 $|A\cap \{i\}| = |B\cap \{i\}|$\\
224 et dans ce cas là $f(g(A)) \geq f(g(B))$\\
225 Donc $A \preccurlyeq _i B$
226 \end{itemize}
227 Donc $\forall x \in I, A \preccurlyeq _i B$
228
229 \subsubsection{Sens 2: Supposons $A \nsubseteq B$}
230 Alors il existe un élement $x \in F$, dans $A$ qui n'est pas dans $B$
231 Et pour cet $x$, $A \npreccurlyeq _x B$
232 Donc $\exists x \in I, A \npreccurlyeq _i B$
233
234 Donc $A \subseteq B \iff \forall x \in I, A \preccurlyeq _i B$
235
236
237\end{homeworkProblem}
238
239\end{document}